package tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        //创建需要的结点
        HeroNode root = new HeroNode(1, "Song");
        HeroNode node2 = new HeroNode(2, "Song2");
        HeroNode node3 = new HeroNode(3, "Song3");
        HeroNode node4 = new HeroNode(4, "Song4");
        HeroNode node5 = new HeroNode(5, "Song5");
        HeroNode node6 = new HeroNode(6, "Song6");
        HeroNode node7 = new HeroNode(7, "Song57");
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        node2.setRight(node7);
        node2.setLeft(node6);
        binaryTree.setRoot(root);
        System.out.println("前");
        binaryTree.preOrder();
        System.out.println("中");
        binaryTree.infixOrder();
        System.out.println("后");
        binaryTree.postOrder();
        System.out.println("前查找");
        HeroNode heroNode = binaryTree.preOrderSearch(node4.getNo());
        System.out.println(heroNode);
        System.out.println("中查找");
        HeroNode heroNode1 = binaryTree.infixOrderSearch(node4.getNo());
        System.out.println(heroNode1);
        System.out.println("后查找");
        HeroNode heroNode2 = binaryTree.postOrderSearch(node4.getNo());
        System.out.println(heroNode2);
        binaryTree.delNode(node6.getNo());
        System.out.println("前");
        binaryTree.preOrder();
    }
}

class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    public HeroNode postOrderSearch(int no) {
        if (root!=null){
           return root.postOrderSearch(no);
        }else  {
            System.out.println("树为空");
            return null;
        }
    }

    public HeroNode infixOrderSearch(int no) {
        if (root!=null){
            return root.infixOrderSearch(no);
        }else  {
            System.out.println("树为空");
            return null;
        }
    }
    public void delNode(int no){
        if (root!=null){
            //先判断是不是这个就是要删除的节点
            if (root.getNo()==no){
                root=null;
            }else {
                root.delNode(no);
            }
        }else {
            System.out.println("空树，无法删除");
        }
    }
}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 遍历方法
     */
    public void preOrder() {
        System.out.println(this);//this 就是自己 输出父节点
        //递归向左子树前序遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.preOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    public HeroNode preOrderSearch(int no) {
        System.out.println("进入preOrderSearch");
        if (this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    public HeroNode infixOrderSearch(int no) {
        HeroNode reNode = null;
        if (this.left != null) {
            reNode = this.left.infixOrderSearch(no);
        }
        if (reNode != null) {
            return reNode;
        }
        System.out.println("进入infix查找");
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            reNode = this.right.infixOrderSearch(no);
        }
        return reNode;
    }

    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
           resNode= this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right!=null){
           resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("进入post查找");
        if (this.no==no){
            return this;
        }
        return  resNode;
    }
    /**
     * 删除节点
     * 叶子 删除节点
     * 非叶子节点 删除子树
     */
    public void delNode(int no){
        if (this.left!=null&&this.left.no==no){
            this.left=null;
            return;
        }
        if (this.right!=null&&this.right.no==no){
            this.right=null;
            return;
        }
        if (this.left!=null){
            this.left.delNode(no);
            return;
        }
        if (this.right!=null){
            this.right.delNode(no);
            return;
        }

    }

}
class arrBinaryTree{
    private int[] arr;//储存数据节点的数组

    public arrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    /**
     *
     * @param index 数组的下标
     */
    public void  preOrder(int index){
        if (arr==null||arr.length==0){
            System.out.println("数组为空，不能按照二叉树的前序遍历");
        }
        if ((index*2+1)<arr.length){
            preOrder(2*index+1);
        }
        if ((index*2+2)<arr.length){
            preOrder(2*index+1);
        }

    }
}